home *** CD-ROM | disk | FTP | other *** search
/ GFX Sensations 1 / Graphic Sensations - Volume 1.iso / tools / amiga / 3d_tools / irit40s.lha / Irit / cagd_lib / cagdzero.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-30  |  9.8 KB  |  357 lines
  1. /******************************************************************************
  2. * CagdZero.c - computes the zeros and extremes of a given object.          *
  3. *******************************************************************************
  4. * Written by Gershon Elber, March 93.                          *
  5. ******************************************************************************/
  6.  
  7. #include "cagd_loc.h"
  8.  
  9. #define SET_DEFAULT_EPSILON    1e-3
  10. #define SET_DEFAULT_EPSILON    1e-3
  11. #define ZERO_APX_EQ(x, y)        (ABS(x - y) < GlblSetEpsilon * 10)
  12. #define MID_RATIO            0.5123456789
  13.  
  14. static CagdPtStruct
  15.     *GlblPtList = NULL;
  16. static CagdRType CrvTMin, CrvTMax,
  17.     GlblSetEpsilon = SET_DEFAULT_EPSILON;
  18.  
  19. static void CagdScalarCrvConstSet(CagdCrvStruct *Crv, CagdRType ConstVal);
  20. static void CagdScalarCrvExtremSet(CagdCrvStruct *Crv);
  21. static void CagdInsertNewParam(CagdRType t);
  22.  
  23. /******************************************************************************
  24. * Computes the zero set of a given curve, in the given axis (1-3 for X-Z).    *
  25. *   Returned is a list of the zero set points holding the parameter values at *
  26. * Pt[0] of each point.                                  *
  27. ******************************************************************************/
  28. CagdPtStruct *CagdCrvZeroSet(CagdCrvStruct *Crv, int Axis, CagdRType Epsilon)
  29. {
  30.     return CagdCrvConstSet(Crv, Axis, Epsilon, 0.0);
  31. }
  32.  
  33. /******************************************************************************
  34. * Computes the extreme set of a given curve, in given axis (1-3 for X-Z).     *
  35. *   Returned is a list of the extreme set points holding the parameter        *
  36. * values at Pt[0] of each point.                          *
  37. *   One could compute the derivative of the curve and find its zero set.      *
  38. * However, for rational curves, this will double the degree and slow down the *
  39. * computation considerably.                              *
  40. ******************************************************************************/
  41. CagdPtStruct *CagdCrvExtremSet(CagdCrvStruct *Crv, int Axis, CagdRType Epsilon)
  42. {
  43.     CagdCrvStruct *CrvW, *CrvX, *CrvY, *CrvZ, *ScalarCrv, *TCrv;
  44.  
  45.     GlblSetEpsilon = Epsilon;
  46.  
  47.     CagdCrvSplitScalar(Crv, &CrvW, &CrvX, &CrvY, &CrvZ);
  48.  
  49.     switch (Axis) {
  50.     case 1:
  51.         if (CrvX)
  52.         ScalarCrv = CrvX;
  53.         else
  54.         FATAL_ERROR(CAGD_ERR_OUT_OF_RANGE);
  55.         break;
  56.     case 2:
  57.         if (CrvY)
  58.         ScalarCrv = CrvY;
  59.         else
  60.         FATAL_ERROR(CAGD_ERR_OUT_OF_RANGE);
  61.         break;
  62.     case 3:
  63.         if (CrvZ)
  64.         ScalarCrv = CrvZ;
  65.         else
  66.         FATAL_ERROR(CAGD_ERR_OUT_OF_RANGE);
  67.         break;
  68.     default:
  69.         FATAL_ERROR(CAGD_ERR_OUT_OF_RANGE);
  70.     }
  71.  
  72.     Crv = CagdCrvMergeScalar(CrvW, ScalarCrv, NULL, NULL);
  73.     if (CrvW)
  74.     CagdCrvFree(CrvW);
  75.     if (CrvX)
  76.     CagdCrvFree(CrvX);
  77.     if (CrvY)
  78.     CagdCrvFree(CrvY);
  79.     if (CrvZ)
  80.     CagdCrvFree(CrvZ);
  81.     
  82.     GlblPtList = NULL;
  83.     if (CAGD_IS_BEZIER_CRV(Crv)) {
  84.     /* We need to save domains. */
  85.     TCrv = CnvrtBezier2BsplineCrv(Crv);
  86.     CagdCrvFree(Crv);
  87.     Crv = TCrv;
  88.     }
  89.  
  90.     CagdCrvDomain(Crv, &CrvTMin, &CrvTMax);
  91.     CagdScalarCrvExtremSet(Crv);
  92.     CagdCrvFree(Crv);
  93.  
  94.     return GlblPtList;
  95. }
  96.  
  97. /******************************************************************************
  98. * Computes the constant set of a given curve, in the given axis (1-3 for X-Z).*
  99. * Returned is a list of the constant set points holding the parameter values  *
  100. * at Pt[0] of each point.                              *
  101. ******************************************************************************/
  102. CagdPtStruct *CagdCrvConstSet(CagdCrvStruct *Crv, int Axis, CagdRType Epsilon,
  103.                                 CagdRType ConstVal)
  104. {
  105.     CagdCrvStruct *CrvW, *CrvX, *CrvY, *CrvZ, *ScalarCrv, *TCrv;
  106.  
  107.     GlblSetEpsilon = Epsilon;
  108.  
  109.     CagdCrvSplitScalar(Crv, &CrvW, &CrvX, &CrvY, &CrvZ);
  110.  
  111.     switch (Axis) {
  112.     case 1:
  113.         if (CrvX)
  114.         ScalarCrv = CrvX;
  115.         else
  116.         FATAL_ERROR(CAGD_ERR_OUT_OF_RANGE);
  117.         break;
  118.     case 2:
  119.         if (CrvY)
  120.         ScalarCrv = CrvY;
  121.         else
  122.         FATAL_ERROR(CAGD_ERR_OUT_OF_RANGE);
  123.         break;
  124.     case 3:
  125.         if (CrvZ)
  126.         ScalarCrv = CrvZ;
  127.         else
  128.         FATAL_ERROR(CAGD_ERR_OUT_OF_RANGE);
  129.         break;
  130.     default:
  131.         FATAL_ERROR(CAGD_ERR_OUT_OF_RANGE);
  132.     }
  133.  
  134.     Crv = CagdCrvMergeScalar(CrvW, ScalarCrv, NULL, NULL);
  135.     if (CrvW)
  136.     CagdCrvFree(CrvW);
  137.     if (CrvX)
  138.     CagdCrvFree(CrvX);
  139.     if (CrvY)
  140.     CagdCrvFree(CrvY);
  141.     if (CrvZ)
  142.     CagdCrvFree(CrvZ);
  143.     
  144.     GlblPtList = NULL;
  145.     if (CAGD_IS_BEZIER_CRV(Crv)) {
  146.     /* We need to save domains. */
  147.     TCrv = CnvrtBezier2BsplineCrv(Crv);
  148.     CagdCrvFree(Crv);
  149.     Crv = TCrv;
  150.     }
  151.  
  152.     CagdCrvDomain(Crv, &CrvTMin, &CrvTMax);
  153.     CagdScalarCrvConstSet(Crv, ConstVal);
  154.     CagdCrvFree(Crv);
  155.  
  156.     return GlblPtList;
  157. }
  158.  
  159. /******************************************************************************
  160. * Computes the zero set of a scalar curve. Curve might be rational.          *
  161. * Assumes open end condition on the curve parametric domain.              *
  162. * Zero set points are append to the GlblPtList point list.              *
  163. ******************************************************************************/
  164. static void CagdScalarCrvConstSet(CagdCrvStruct *Crv, CagdRType ConstVal)
  165. {
  166.     int i,
  167.     Len = Crv -> Length,
  168.         Sign = 0;
  169.     CagdRType
  170.     *ScalarPts = Crv -> Points[1],
  171.     *ScalarWPts = Crv -> Points[0];
  172.  
  173.     if (CagdCrvPosNegWeights(Crv)) {
  174.     i = 0;                  /* Force subdivision of the curve. */
  175.     }
  176.     else {
  177.     for (i = 0; i < Len; i++) {
  178.         CagdRType
  179.         V = (ScalarWPts ? ScalarPts[i] / ScalarWPts[i] :
  180.                                   ScalarPts[i]) - ConstVal;
  181.         int NewSign = SIGN(V);
  182.  
  183.         if (Sign * NewSign < 0)
  184.         break;
  185.         else if (NewSign)
  186.         Sign = NewSign;
  187.     }
  188.     }
  189.  
  190.     if (i < Len) {
  191.     CagdRType TMin, TMax, TMid;
  192.  
  193.     /* Control polygon is both positive and negative. */
  194.     CagdCrvDomain(Crv, &TMin, &TMax);
  195.     TMid = TMin * MID_RATIO + TMax * (1.0 - MID_RATIO);
  196.  
  197.     if (TMax - TMin < GlblSetEpsilon / 5.0) {    /* Small enough - stop. */
  198.         CagdInsertNewParam((TMax + TMin) / 2.0);
  199.     }
  200.     else {                          /* Needs to subdiv. */
  201.         CagdCrvStruct
  202.             *Crv1 = CagdCrvSubdivAtParam(Crv, TMid),
  203.         *Crv2 = Crv1 -> Pnext;
  204.  
  205.         CagdScalarCrvConstSet(Crv1, ConstVal);
  206.         CagdScalarCrvConstSet(Crv2, ConstVal);
  207.  
  208.         CagdCrvFree(Crv1);
  209.         CagdCrvFree(Crv2);
  210.     }
  211.     }
  212. }
  213.  
  214. /******************************************************************************
  215. * Computes the extrem set of a scalar curve. Curve might be rational.          *
  216. * Assumes open end condition on the curve parametric domain.              *
  217. * Extreme set points are append to the GlblPtList point list.              *
  218. ******************************************************************************/
  219. static void CagdScalarCrvExtremSet(CagdCrvStruct *Crv)
  220. {
  221.     int i,
  222.     Len = Crv -> Length,
  223.         Sign = 0;
  224.     CagdRType
  225.     *ScalarPts = Crv -> Points[1],
  226.     *ScalarWPts = Crv -> Points[0];
  227.  
  228.     if (CagdCrvPosNegWeights(Crv)) {
  229.     i = 0;                  /* Force subdivision of the curve. */
  230.     }
  231.     else {
  232.     CagdRType
  233.         PrevV = ScalarWPts ? ScalarPts[0] / ScalarWPts[0] : ScalarPts[0];
  234.  
  235.     for (i = 0; i < Len; i++) {
  236.         CagdRType
  237.         V = (ScalarWPts ? ScalarPts[i] / ScalarWPts[i] : ScalarPts[i]),
  238.         DV = V - PrevV;
  239.  
  240.         int NewSign = SIGN(DV);
  241.  
  242.         if (Sign * NewSign < 0)
  243.         break;
  244.         else if (NewSign)
  245.         Sign = NewSign;
  246.  
  247.         PrevV = V;
  248.     }
  249.     }
  250.  
  251.     if (i < Len) {
  252.     CagdRType TMin, TMax, TMid;
  253.  
  254.     /* Control polygon is both increasing and decreasing. */
  255.     CagdCrvDomain(Crv, &TMin, &TMax);
  256.     TMid = TMin * MID_RATIO + TMax * (1.0 - MID_RATIO);
  257.  
  258.     if (TMax - TMin < GlblSetEpsilon / 5.0) {    /* Small enough - stop. */
  259.         CagdInsertNewParam((TMax + TMin) / 2.0);
  260.     }
  261.     else {                          /* Needs to subdiv. */
  262.         CagdCrvStruct
  263.             *Crv1 = CagdCrvSubdivAtParam(Crv, TMid),
  264.         *Crv2 = Crv1 -> Pnext;
  265.  
  266.         CagdScalarCrvExtremSet(Crv1);
  267.         CagdScalarCrvExtremSet(Crv2);
  268.  
  269.         CagdCrvFree(Crv1);
  270.         CagdCrvFree(Crv2);
  271.     }
  272.     }
  273.     else {
  274.     CagdRType V1, V2, TMin, TMax;
  275.  
  276.     CagdCrvDomain(Crv, &TMin, &TMax);
  277.  
  278.     /* This segment is monotone. Test if end points are extremes. */
  279.     V1 = ScalarWPts ? ScalarPts[0] / ScalarWPts[0] : ScalarPts[0];
  280.     V2 = ScalarWPts ? ScalarPts[1] / ScalarWPts[1] : ScalarPts[1];
  281.     if (APX_EQ(V1, V2))
  282.         CagdInsertNewParam(TMin);
  283.  
  284.     V1 = ScalarWPts ? ScalarPts[Len - 2] / ScalarWPts[Len - 2]
  285.             : ScalarPts[Len - 2];
  286.     V2 = ScalarWPts ? ScalarPts[Len - 1] / ScalarWPts[Len - 1]
  287.             : ScalarPts[Len - 1];
  288.     if (APX_EQ(V1, V2))
  289.         CagdInsertNewParam(TMax);
  290.     }
  291. }
  292.  
  293. /******************************************************************************
  294. * Returns TRUE iff the Crv is not rational or rational with weights that are  *
  295. * entirely positive or entirely negative.                      *
  296. ******************************************************************************/
  297. CagdBType CagdCrvPosNegWeights(CagdCrvStruct *Crv)
  298. {
  299.     int i;
  300.     CagdBType HasNeg, HasPos;
  301.     CagdRType
  302.     *Weights = Crv -> Points[0];
  303.  
  304.     if (Weights == NULL)
  305.     return FALSE;                   /* Curve is not rational. */
  306.  
  307.     for (HasNeg = HasPos = FALSE, i = Crv -> Length - 1; i >= 0; i--) {
  308.     HasNeg |= *Weights < 0.0;
  309.     HasPos |= *Weights++ > 0.0;
  310.     }
  311.  
  312.     return HasNeg && HasPos;
  313. }
  314.  
  315. /******************************************************************************
  316. * Insert a single t value into existing GlblPtList, provided no equal t value *
  317. * exists already in the list. List is order incrementally.              *
  318. ******************************************************************************/
  319. static void CagdInsertNewParam(CagdRType t)
  320. {
  321.     CagdPtStruct *PtTmp, *PtLast, *Pt;
  322.  
  323.     if (APX_EQ(t, CrvTMin) || APX_EQ(t, CrvTMax))
  324.     return;
  325.  
  326.     Pt = IritMalloc(sizeof(CagdPtStruct));
  327.     Pt -> Pt[0] = t;
  328.     Pt -> Pnext = NULL;
  329.  
  330.     if (GlblPtList) {
  331.     for (PtTmp = GlblPtList, PtLast = NULL;
  332.          PtTmp != NULL;
  333.          PtLast = PtTmp, PtTmp = PtTmp -> Pnext) {
  334.         if (ZERO_APX_EQ(PtTmp -> Pt[0], t)) {
  335.             IritFree(Pt);
  336.         return;
  337.         }
  338.         if (PtTmp -> Pt[0] > t)
  339.             break;
  340.     }
  341.     if (PtTmp) {
  342.         /* Insert the new point in the middle of the list. */
  343.         Pt -> Pnext = PtTmp;
  344.         if (PtLast)
  345.         PtLast -> Pnext = Pt;
  346.         else
  347.         GlblPtList = Pt;
  348.     }
  349.     else {
  350.         /* Insert the new point as the last point in the list. */
  351.         PtLast -> Pnext = Pt;
  352.     }
  353.     }
  354.     else
  355.         GlblPtList = Pt;
  356. }
  357.